package com.atwulidun.huffmantree;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

public class HuffmanTreeDemo {
    public static void main(String[] args) {
        int[] arr = { 13, 7, 8, 3, 29, 6, 1 };
        HuffmanTree huffmanTree = new HuffmanTree(arr);
        huffmanTree.preOrderList();// 67 29 38 15 7 8 23 10 4 1 3 6 13
    }
}

class HuffmanTree {
    private final Node root;

    // 在实例化对象的时候，通过调用自带的createHuffmanTree方法并利用传进来的arr生成一棵赫夫曼树，并对root进行赋值
    public HuffmanTree(int[] arr) {
        root = createHuffmanTree(arr);
    }

    // 通过数组arr生成赫夫曼树的方法
    public Node createHuffmanTree(int[] arr) {
        // 一、首先将数组arr的每个元素里的值保存到Node里，再把Node添加到List中
        // 创建一个list
        List<Node> list = new ArrayList<>();
        for (int i : arr) {
            list.add(new Node(i));
        }

        // 二、循环进行，当list中只有一个元素时退出循环，此时已经生成了一棵赫夫曼树
        while (list.size() > 1) {
            // 1.对list进行升序排序
            Collections.sort(list);

            // 2.根据list最左边的两个结点形成一棵新的赫夫曼树，权值为前面两者权值之和
            Node leftNode = list.get(0);
            Node rightNode = list.get(1);

            Node parentNode = new Node(leftNode.getValue() + rightNode.getValue());
            // 特别注意：以下两句建立父结点和子结点关系的语句特别容易漏！！！！！！！！！
            parentNode.setLeft(leftNode);
            parentNode.setRight(rightNode);

            // 3.把leftNode和rightNode在list中删除，把parentNode添加到list中
            list.remove(leftNode);
            list.remove(rightNode);
            list.add(parentNode);
        }

        // 三、返回生成的赫夫曼树的根结点
        return list.get(0);
    }

    // 定义一个前序遍历的方法
    public void preOrderList() {
        if (root == null) {
            System.out.println("赫夫曼树为空！");
        } else {
            root.preOrderList();
        }
    }
}

// 实现Comparable接口，则可以利用集合的方法对Node进行排序
class Node implements Comparable<Node> {
    private int value;
    private Node left;
    private Node right;

    public Node(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    // 定义一个前序遍历的方法
    public void preOrderList() {
        System.out.print(value + " ");
        if (left != null) {
            left.preOrderList();
        }
        if (right != null) {
            right.preOrderList();
        }
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    @Override
    public int compareTo(Node o) {
        return value - o.value;// 当前对象的值减去传进来对象的值为升序排序
    }
}

